//
// Created by isabella on 25-5-26.
//
#include <common.h>

class Solution {
    vector<int> parent;
    vector<int> rank;
    int n;

public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        this->parent.resize(isConnected.size());
        this->rank.resize(isConnected.size());
        this->n = isConnected.size();

        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
        for (int i = 0; i < isConnected.size(); i++) {
            for (int j = 0; j < isConnected[i].size(); j++) {
                if (isConnected[i][j] == 1) {
                    u(i,j);
                }
            }
        }
        int cnt = 0;
        for(int i=0;i<n;i++) {
            if(parent[i] == i) {
                cnt++;
            }
        }
        return cnt;
    }

private:
    void u(int x,int y) {
        int xs=find(x);
        int ys=find(y);
        if(rank[x]>=rank[y]) {
            rank[xs]+=rank[y];
            parent[ys]=xs;
        }else {
            rank[ys]+=rank[x];
            parent[xs]=ys;
        }
    }

    int find(int x) {
        while(x!=parent[x]) {
            x = parent[x];
        }
        return x;
    }
};
int main() {
    return 0;
}